#!/usr/bin/env python
import sys
import re
import pickle

dict = {}
g_generate = 0
g_idx_file = ""
g_depth = 1000 # Is this enough?
g_path = ""
g_flist = ""
g_root = ""

# print out a tree with specified root
indent = 0
call_path = set() # for detecting recursive call
accessed = set()  # for reducing duplicated result
last_stack =[]	  # a stack keeping whether the cording depth on call path is last

def show_tree(root, is_last):
    global dict, indent, call_path, accessed, g_depth, last_stack

    if (root):
        str = ""
        if indent != 0:
            cnt = 0
            for i in last_stack:
                cnt += 1
                if cnt == len(last_stack):
                    if i == 0:
                        str += "|-- "
                    else:
                        str += "`-- "
                else:
                    if i == 0:
                        str += "|   "
                    else:
                        str += "    "

        str += root
        if root in call_path:
            str += " (r)"
            print str
            return
        elif root in accessed:
            str += " (^)"
            print str
            return

        # depth control
        if indent >= g_depth - 1:
            str += " ..."
            print str
            return

        print str

        call_path.add(root)
        accessed.add(root)

        if root in dict.keys():
            indent = indent + 1

            cnt = 0
            num = len(dict[root])

            for callee in dict[root]:
                last = 0
                cnt += 1
                if (cnt == num):
                    last = 1

                last_stack.append(last)
                show_tree(callee, last)
                last_stack.pop()

            indent = indent - 1

        call_path.remove(root)

def dump_dic():
    global dict
    for k in dict.keys():
        print k
        callees = dict[k]
        for callee in callees:
            print "    ", callee

def usage():
    print """usage: ct [<options>] <func_name>

This program parses the RTL output of gcc and generate a call tree

Options:
  -h    	Show this usage help.
  -V 		Show version information.

  -g		Generate index file.
  -f <file>     File name of the index file.
  -d <depth>	Depth of call tree
  -l <file>	File name of list file
"""

def gen_idx():
    global g_flist
    global dict
    file_list_h = open(g_flist, 'r')

    # regular expresion to find a caller
    caller_r = re.compile("^;; Function\s+([a-zA-Z_][a-zA-Z_0-9]*)")
    # regular expresion to find a callee
    # some identifiers got 1 or 2 '^' in front of them. (Why?)
    callee_r = re.compile("call.*\(\"\^*([a-zA-Z_][a-zA-Z_0-9]*)\"\)")

    for file in file_list_h:
        file_h = open(file.rstrip(), 'r') # have to remove '\n' at the end before open
        for line in file_h:
            m = caller_r.search(line)
            if (m):
                caller = m.group(1)
                dict[caller] = []
                continue

            m = callee_r.search(line)
            if (m):
                callee = m.group(1)

                # this may be slow for large project
                # replace it with set
                if callee not in dict[caller]:
                    dict[caller].append(callee)
                continue
        file_h.close()

    file_list_h.close()
    f = open(g_idx_file, 'wb')
    pickle.dump(dict, f)
    f.close()



def main():
    global g_generate, g_idx_file, g_depth, g_path, g_flist, g_root
    global dict

    if len(sys.argv) == 1:
        usage()
        sys.exit(1)

    for arg in sys.argv[1:]:
        if arg=="-h":
            usage()
            sys.exit(1)
        if arg=="-g":
            g_generate = 1
        elif arg=="-f":
            g_idx_file = sys.argv[sys.argv.index("-f") + 1]
        elif arg=="-d":
            g_depth = int(sys.argv[sys.argv.index("-d") + 1])
        elif arg=="-l":
            g_flist = sys.argv[sys.argv.index("-l") + 1]
        else:
            g_root = arg

    # generate index file
    if g_generate != 0:
        gen_idx()
        sys.exit(0)

    else:
        f = open(g_idx_file, 'rb')
        dict = pickle.load(f)
        f.close()
        show_tree(g_root, 0)

main()

